<!DOCTYPE html><html><head><meta charset="UTF-8"><title>Tetris Hashing Comments</title><style>
    .comment {
      overflow: hidden;
      padding: 18px 0 7px 0;
      clear: both;
    }

    .comment + .comment {
      border-top: 1px solid #e8e8e8;
    }

    .comment > .json {
      display: none;
    }

    .comment-box {
      background-color: #fffbe1;
      overflow: hidden;
      padding: 6px 12px;
      margin-bottom: 8px;
    }

    .reply-box {
      background-color: #eff2f9;
      padding: 6px 12px 6px 6px;
      overflow: hidden;
      margin-bottom: 8px;
    }

    .user-name {
      font-weight: bold;
      padding-right: 10px;
    }

    .comment > .author-picture {
      float: left;
      padding: 0 20px;
    }

    .reply-box > .author-picture {
      float: left;
      padding: 0 6px;
    }

    .comment-deleted {
      color: red;
      padding-right: 10px;
    }

    .author-picture + div, .user-name, .user-name + .comment-deleted, .user-name + .comment-action {
      float: left;
    }

    .created-date {
      color: #999;
    }

    .comment-box .comment-content {
      clear: both;
    }

    .comment-box > .created-date {
      float: right;
    }

    .reply-box .created-date {
      clear: both;
    }

    .comment-context-intro {
      color: #999;
      clear: both;
    }

    .comment-context-value {
      border-left: 1px solid #ccc;
      font-style: italic;
      padding: 3px 10px 3px 10px;
    }

    .comment-action {
      font-style: italic;
    }

    .comment-status {
      font-style: italic;
      color: green;
      float: left;
      font-weight: bold;
      padding-right: 10px;
    }
  </style></head><body><section class="header"><h1>Tetris Hashing - Drive File Comments</h1></section><section><div id="AAAABoWReNo" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GiBZR6HQdFvEqJ958KmidLmZE1kUSd9N9mzEFY74A=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Felix Chern</div><div class="comment-status"></div><div class="created-date">Feb 26, 2018, 11:43 PM</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">average two cache misses per lookup</div></div><div class="comment-content">Collect the histogram for cache misses (probe length) can visualize average lookup time and worst case lookup time. See <a href="https://www.google.com/url?q=http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/&amp;sa=D&amp;source=docs&amp;ust=1653194620879816&amp;usg=AOvVaw2EDw0sf4k9EGYRE8kgunV6" data-rawhref="http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/" target="_blank">http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/</a></div></div><div class="reply-list"></div></div></div><div id="AAAABjX7rho" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a/AATXAJx_xEpWIMbAlHYzSQpNB2EXP4ZFUkQauchG7aAaaA=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Harshal Tushar Lehri</div><div class="comment-status"></div><div class="created-date">Jan 22, 2018, 5:23 PM</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add tab</span></div></div></div><div class="reply-list"><div id="AAAABjX7rhs" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a/AATXAJx_xEpWIMbAlHYzSQpNB2EXP4ZFUkQauchG7aAaaA=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Harshal Tushar Lehri</div><div class="comment-action">Rejected suggestion</div><div class="comment-content"></div><div class="created-date">Jan 22, 2018, 5:23 PM</div></div></div></div></div></div><div id="AAAABjMvcuk" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GgubsLFEeLeu4GbH3O0sO-EXaMFAyMoelEr0ro1=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">David Applegate</div><div class="comment-status"></div><div class="created-date">Jan 19, 2018, 4:48 PM(edited: Jan 19, 2018, 7:13 PM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">f(x) = x + 7</div></div><div class="comment-content">More precisely, the hash function in this example is f(x) = (x+7) % 10.<br>If you use a table of size 9 or 11, it fails (size 9: 0 and 27 collide.  Size 11: 0 and 88 collide).  Also, you could just as readily use f(x)=x%10 (the +7 is useless).</div></div><div class="reply-list"><div id="AAAABjMvc5M" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-content">I was wondering about this when I was writing it; does the hash function really include the modulus? After some thinking I eventually concluded that since java&#39;s hashCode() doesn&#39;t require its output to be in a certain range, that people must think the modulus is outside the hash function. Should I change it here?</div><div class="created-date">Jan 19, 2018, 7:13 PM</div></div></div></div></div></div><div id="AAAABjMvcFo" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a/AATXAJzTvdTQT4AaO-ObHBjAgjtSKp_9TrFqH1G5R3n1=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Pavel Kalinnikov</div><div class="comment-status"></div><div class="created-date">Jan 18, 2018, 10:00 AM</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Format:</span> indent first line</div></div></div><div class="reply-list"></div></div></div><div id="AAAABjL8Bt4" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14Ggqm56nNl_4lB4gK4lorydxaXw4IBCtx7AcaS3t=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Jan Wassenberg</div><div class="comment-status"></div><div class="created-date">Jan 18, 2018, 12:39 AM(edited: Feb 26, 2018, 11:39 PM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">% numSecondaryTables</div></div><div class="comment-content">64-bit modulo is super expensive, 30-100 cycles, might even block other instructions for 20-80 cycles. Can you use this instead?<br> <a href="https://www.google.com/url?q=https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/&amp;sa=D&amp;source=docs&amp;ust=1653194620876869&amp;usg=AOvVaw2iv13ZYx7u5lwP4hvenlkD" data-rawhref="https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/" target="_blank">https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/</a></div></div><div class="reply-list"><div id="AAAABjL8Bt8" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-content">I had no idea it was so expensive! I&#39;ll try it out and let you know here how it goes, thanks a bunch for pointing this out!</div><div class="created-date">Jan 18, 2018, 12:48 AM</div></div></div><div id="AAAABjMvcD4" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-content">Looks like it works, but the cost shoots way up (184n space usage). It seems the algorithm&#39;s having a lot of trouble when it&#39;s trying to calculate the secondary hash sets, in the place where it keeps increasing the size by 1 until it gets something without collisions. I suspect there&#39;s something about modulus that really shuffles things up, giving us a better chance to get a perfect secondary hash table faster.<br><br>Trying now to think of other ways we can get around this expensive modulus operation...</div><div class="created-date">Jan 18, 2018, 8:20 AM</div></div></div><div id="AAAABjMvcD8" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-content">Got an idea: For the top level hash instead of having a length N/4, we can do the next power of two after N/4, that should maintain the roughly linear nature of the algorithm, and instead of a modulus we can use an &amp; instead. It might interfere with the mulligans though. Much to think about.</div><div class="created-date">Jan 18, 2018, 8:23 AM(edited: Jan 18, 2018, 8:24 AM)</div></div></div><div id="AAAABoWReNg" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14Gg9EN0E1BEUcixdFMA3kRN5hjXQ1XQSCUQ2VEfKFw=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Felix Chern</div><div class="comment-content"><a href="https://www.google.com/url?q=http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/&amp;sa=D&amp;source=docs&amp;ust=1653194620864240&amp;usg=AOvVaw0_wls6VvZQxeGT9Z5acUpA" data-rawhref="http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/" target="_blank">http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/</a><br>I reasoned about why lemire&#39;s modulo works bad when combined with linear probing. The solution is simple: use power of 2 modulo first, then use lemire&#39;s approach (I call it a stretch).</div><div class="created-date">Feb 26, 2018, 11:39 PM</div></div></div></div></div></div><div id="AAAABlO5jQc" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:55 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“;”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRw" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:55 PM</div></div></div></div></div></div><div id="AAAABlO5jQY" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:55 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“;”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRs" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:55 PM</div></div></div></div></div></div><div id="AAAABlO5jQU" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:54 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“;”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRo" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:54 PM</div></div></div></div></div></div><div id="AAAABlO5jQQ" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:54 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“;”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRk" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:54 PM</div></div></div></div></div></div><div id="AAAABlO5jQM" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:54 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“;”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRg" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:54 PM</div></div></div></div></div></div><div id="AAAABlO5jQE" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GhgAzaI8SFKTP9zsGoYFBXiwZNpuS0jgdEq3-mwJg=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Andrew Helsley</div><div class="comment-status"></div><div class="created-date">Jan 17, 2018, 7:50 PM(edited: Jan 17, 2018, 7:54 PM)</div><div class="comment-content"><div style="font-size:13px;color:#333"><span style="font-weight:bold">Add:</span> <span style="white-space:pre-line;color:#777;font-style:italic">“-”</span></div></div></div><div class="reply-list"><div id="AAAABlO5jRc" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Accepted suggestion</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 7:54 PM</div></div></div></div></div></div><div id="AAAABlUoq8I" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Evan Ovadia</div><div class="comment-status">Resolved</div><div class="created-date">Jan 16, 2018, 6:27 PM(edited: Jan 17, 2018, 12:10 AM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">.</div></div><div class="comment-content">todo: mention the compact version, which is (2log2(N) - 3)N bits overhead, but more instructions</div></div><div class="reply-list"><div id="AAAABd9FLOU" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Marked as resolved</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 12:10 AM</div></div></div></div></div></div><div id="AAAABlUoq7k" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Evan Ovadia</div><div class="comment-status">Resolved</div><div class="created-date">Jan 16, 2018, 6:27 PM(edited: Jan 17, 2018, 12:10 AM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">1.4N pointers</div></div><div class="comment-content">todo: update this, i think its more accurate to say 0.65N words</div></div><div class="reply-list"><div id="AAAABd9FLOQ" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Marked as resolved</div><div class="comment-content"></div><div class="created-date">Jan 17, 2018, 12:10 AM</div></div></div></div></div></div><div id="AAAABlUoq6Q" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Evan Ovadia</div><div class="comment-status">Resolved</div><div class="created-date">Jan 16, 2018, 6:22 PM(edited: Jan 16, 2018, 6:26 PM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">1.4N pointers</div></div><div class="comment-content">todo: might actually be 0.4N, depending on interpretation...</div></div><div class="reply-list"><div id="AAAABlUoq7I" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Marked as resolved</div><div class="comment-content"></div><div class="created-date">Jan 16, 2018, 6:26 PM</div></div></div></div></div></div><div id="AAAABlV_fy4" class="comment"><div class="json">null</div><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="48" height="48" alt="Author profile image"></div><div class="comment-data"><div class="comment-box"><div class="user-name">Evan Ovadia</div><div class="comment-status">Resolved</div><div class="created-date">Jan 15, 2018, 11:34 PM(edited: Jan 16, 2018, 6:11 PM)</div><div class="comment-context"><div class="comment-context-intro">Selected text:</div><div class="comment-context-value">https://pastebin.com/UhkPdCCf</div></div><div class="comment-content">update this and benchmark</div></div><div class="reply-list"><div id="AAAABlUoq58" class="reply-box"><div class="author-picture"><img src="https://lh3.googleusercontent.com/a-/AOh14GjoOXwuji1Q0p6FX0IRu-PBtgN-CxWdF8wvbNemn1A=s50-c-k-no" width="24" height="24" alt="Author profile image"></div><div class="reply-data"><div class="user-name">Evan Ovadia</div><div class="comment-action">Marked as resolved</div><div class="comment-content"></div><div class="created-date">Jan 16, 2018, 6:11 PM</div></div></div></div></div></div></section></body></html>